package com.fr.lintcode;

/**
*作者：furong
*日期：2017年3月7日
*时间：上午11:32:01
*/
public class Q439 {
    /**
     *@param A: a list of integer
     *@return: The root of Segment Tree
     */
    public SegmentTreeNode build(int[] A) {
        if (A == null || A.length <= 0) {
            return null;
        }
        SegmentTreeNode root = build(0, A.length - 1);
        max(root, A);
        return root;
    }

    private SegmentTreeNode build(int start, int end) {
        SegmentTreeNode node = new SegmentTreeNode(start, end);
        if (start < end) {
            int mid = (start + end) / 2;
            node.left = build(start, mid);
            node.right = build(mid + 1, end);
        }
        return node;
    }

    private int max(SegmentTreeNode node, int[] a) {
        if (node == null) {
            return 0;
        } else if (node.start == node.end) {
            node.max = a[node.start];
            return node.max;
        }
        int left = max(node.left, a);
        int right = max(node.right, a);
        node.max = Math.max(left, right);
        return node.max;
    }
}
